package com.huangyi;

import java.util.Arrays;

public class Main {
    public static void main(String[] args) {
        // 测试用例
    }

    // 最长数对链
    static class Solution {
        public int findLongestChain(int[][] pairs) {
            int n = pairs.length;

            // 按右端点排序
            Arrays.sort(pairs, (a, b) -> a[1] - b[1]);

            // dp[i] 表示以 pairs[i] 结尾的最长链长度
            int[] dp = new int[n];
            Arrays.fill(dp, 1);

            // 状态转移
            for (int i = 1; i < n; i++) {
                for (int j = 0; j < i; j++) {
                    if (pairs[j][1] < pairs[i][0]) {
                        dp[i] = Math.max(dp[i], dp[j] + 1);
                    }
                }
            }

            // 找最大值
            int ret = 1;
            for (int i = 0; i < n; i++) {
                ret = Math.max(ret, dp[i]);
            }
            return ret;
        }
    }
}